//链表分割
//现有一链表的头指针 ListNode* pHead，给一定值x，
//编写一段代码将所有小于x的结点排在其余结点之前，
//且不能改变原来的数据顺序，返回重新排列后的链表的头指针
#include<stdio.h>
#include<stdlib.h>


struct ListNode
{
	int val;
	struct ListNode* next;
};

void SLTNodePrintf(struct ListNode* ps)
{
	struct ListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

//将小于x的结点尾插到第一条链表(带哨兵)
//将大于x的结点尾插到第二条链表 
//然后连接
struct ListNode*  partition(struct ListNode* pHead, int x)
{
	//哨兵
	struct ListNode* lhead = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* ghead = (struct ListNode*)malloc(sizeof(struct ListNode));

	struct ListNode*  ltail = lhead;
	struct ListNode*  gtail = ghead;
	struct ListNode* cur = pHead;

	while (cur)
	{
		//判断
		if (cur->val < x)
		{
			//尾插(不带哨兵要考虑空链表的情况)
			ltail->next = cur;
			ltail = ltail->next;
		}
		else
		{
			//尾插
			gtail->next = cur;
			gtail = gtail->next;
		}
		cur = cur->next;
	}

	//连接 (带哨兵 指向gtail->next)
	ltail->next = ghead->next;
	//连接后处理尾部(不置空会出现带环)
	gtail->next = NULL;
	//释放哨兵
	//释放之前记录新头结点 不然找不到
	struct ListNode* newhead = lhead->next;
	free(lhead);
	free(ghead);
	return  newhead;

}



int main()
{
	struct ListNode* n1 = malloc(sizeof(struct ListNode));
	struct ListNode* n2 = malloc(sizeof(struct ListNode));
	struct ListNode* n3 = malloc(sizeof(struct ListNode));
	struct ListNode* n4 = malloc(sizeof(struct ListNode));

	n1->val = 1;
	n2->val = 3;
	n3->val = 2;
	n4->val = 1;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	SLTNodePrintf(n1);

	struct ListNode* newnode = partition(n1,2);
	SLTNodePrintf(newnode);

	return 0;
}